package Offer07;

/**
 * 重建二叉树
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 *
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * @author 23737
 * @time 2021.11.01
 */
public class Test {
    public static void main(String[] args) {

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

//B站大佬题解
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return help(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }

    private TreeNode help(int[] preorder, int[] inorder, int left, int right, int left1, int right1) {
        if(left >= preorder.length || left1>= inorder.length || left>right||left1>right1){
            return null;
        }
        int value = preorder[left];
        TreeNode node = new TreeNode(value);
        int count = left1;
        while(inorder[count]!=value)
            count++;
        count-=left1;

        node.left = help(preorder,inorder,left+1,left+count,left1,left1+count-1);
        node.right = help(preorder,inorder,left+count+1,right,left1+count+1,right1);
        return node;
    }
}
